class Solution {
    public int numSquares(int n) {
        /**
         * 完全背包问题
         * n：背包总体积
         * i：物品编号
         * i^2：物品体积
         * 1：物品价值
         * 求：min
         */
         List<Integer> items = new ArrayList<>();
         for (int i = 1; i*i <= n; i++) {
             items.add(i*i);
         }
         int m = items.size();
         /**
          * f(i,j) 表示存满j体积的最小价值
          * i 表示前i个物品中取
          * j 表示已选物品总体积
          * f(i,j) = f(i-1,j) 第i个物品没选
          * f(i,j) = f(i,j-i^2) + 1 第i个物品选了
          */
        /* 简化前
        int[][] f = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[i][j] = n+1;
            }
        }
        f[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[i][j] = f[i-1][j];
            }
            int curr = items.get(i-1);
            for (int j = curr; j <= n; j++) {
                f[i][j] = Math.min(f[i][j], f[i][j-curr] + 1);
            }
        }
        return f[m][n];
        */
        int[] f = new int[n+1];
        Arrays.fill(f, n+1);
        f[0] = 0;
        for (int i = 1; i <= m; i++) {
            int curr = items.get(i-1);
            for (int j = curr; j <= n; j++) {
                f[j] = Math.min(f[j], f[j-curr]+1);
            }
        }
        return f[n];
    }
}
